//
// Created by francklinson on 2021/5/22.
//
/*给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。

定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自 nums2。

找到和最小的 k 对数字(u1,v1), (u2,v2) ... (uk,vk)。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/




#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
    struct Node {
    public:
        int x;
        int y;
        int sum;

        bool operator<(const Node &rhs) const {
            return this->sum > rhs.sum;
        }

        Node(int x, int y, int sum) : x(x), y(y), sum(sum) {}
    };

public:
    vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k) {
        priority_queue<Node> pq; // 小堆顶
        int m = (int) nums1.size();
        int n = (int) nums2.size();
        // 将A和B[0]加和的结果入队
        for (int i = 0; i < nums1.size(); ++i) {
            pq.emplace(i, 0, nums1[i] + nums2[0]);
        }
        // 逐个出队 堆顶的[x,y+1]的位置入队
        vector<vector<int>> ans;
        for (int i = 0; i < min(k, m * n); ++i) {
            auto temp = pq.top();
            ans.push_back(vector<int>{nums1[temp.x], nums2[temp.y]});
            pq.pop();
            if (temp.y + 1 < nums2.size()) {
                pq.emplace(temp.x, temp.y + 1, nums1[temp.x] + nums2[temp.y + 1]);
            }
        }
        return ans;

    }
};

int main() {
    vector<int> n1{1, 2};
    vector<int> n2{3};
    Solution sol;
    auto ans = sol.kSmallestPairs(n1, n2, 3);
    for (auto &x:ans) {
        cout << x[0] << " " << x[1] << endl;
    }
    return 0;
}